package cn.xaut.动态规划;

import java.util.Arrays;

/**
 * 174. 地下城游戏
 */
public class demo174 {
    
    int[][] memo;   // 备忘录，消除重叠子问题
    // 主函数
    public int calculateMinimumHP(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;
        memo = new int[m][n];
        for (int[] row : memo)
            Arrays.fill(row, -1);

        return dp(grid, 0, 0);
    }

    // 从 (i, j) 到达右下角，需要的初始血量至少是多少
    public int dp(int[][] grid, int i, int j) {

        int m = grid.length;
        int n = grid[0].length;
        
        // 递归终止条件
        if (i == m - 1 && j == n - 1) 
            return grid[i][j] >= 0 ? 1 : -grid[i][j] + 1;
        if (i >= m || j >= n)
            return Integer.MAX_VALUE;
        if (memo[i][j] != -1)
            return memo[i][j];

        // 递归过程
        int res = Math.min(dp(grid, i + 1, j), dp(grid, i, j + 1)) - grid[i][j];
        // 骑士的生命值至少为1
        memo[i][j] = Math.max(res, 1);
        
        return memo[i][j];
    }

    // 动态规划——迭代解法
    public int calculateMinimumHP2(int[][] grid) {
        
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n]; // 从grid[i][j]到达终点（右下角）所需的最少生命值是dp(grid, i, j)。
        
        // 基础状态
        dp[m - 1][n - 1] = grid[m - 1][n - 1] >= 0 ? 1 : -grid[m - 1][n - 1] + 1;
        for (int i = m - 2; i >= 0; i --)
            dp[i][n - 1] = Math.max(dp[i + 1][n - 1] - grid[i][n - 1], 1);
        for (int j = n - 2; j >= 0; j --)
            dp[m - 1][j] = Math.max(dp[m - 1][j + 1] - grid[m - 1][j], 1);
        
        // 状态转移
        for (int i = m - 2; i >= 0; i --) {
            for (int j = n - 2; j >= 0; j --) 
                dp[i][j] = Math.max(Math.min(dp[i + 1][j], dp[i][j + 1]) - grid[i][j], 1);
        }

        return Math.max(dp[0][0], 1);
    }

    public static void main(String[] args) {

        // 测试
        int[][] grid = new int[][]{{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}};
        System.out.println(new demo174().calculateMinimumHP(grid));     // 7
        System.out.println(new demo174().calculateMinimumHP2(grid));    // 7
    }
}
